package leetcode.map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.TreeSet;
/**
 * 
 * @Title: Solution349.java 
 * @Package leetcode.set 
 * @Description: 350. 两个数组的交集 II
 * @author CandyWall   
 * @date 2021年1月6日 下午10:39:19 
 * @version V1.0
 */
public class Solution350_v1 {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 统计第一个数组中的所有元素出现的次数
        HashMap<Integer, Integer> numsCountMap = new HashMap<>();
        for(int num1 : nums1) {
            if(!numsCountMap.containsKey(num1)) {
                numsCountMap.put(num1, 1);
            } else {
                numsCountMap.put(num1, numsCountMap.get(num1) + 1);
            }
        }
        
        // 遍历第二个数组
        int k = 0;
        for(int num2 : nums2) {
            // 如果第二个数组中的元素在第一个数组中出现
            if(numsCountMap.containsKey(num2)) {
                // 将这个元素存起来
                nums1[k++] = num2;
                // 获取这个元素在第一个数组中出现的次数
                int count = numsCountMap.get(num2);
                // 如果出现的次数大于1，就减去1，并保存到映射中
                if(count > 1) {
                    numsCountMap.put(num2, count - 1);
                } 
                // 如果出现的次数等于1，就从映射中移除这个元素
                else { //count == 1
                    numsCountMap.remove(num2);
                }
            }
        }
        
        return Arrays.copyOfRange(nums1, 0, k);
    }

    
    public static void main(String[] args) {
        /*int[] nums1 = {1, 2, 2, 1};
        int[] nums2 = {2, 2};*/
        int[] nums1 = {4,9,5};
        int[] nums2 = {9,4,9,8,4};
        int[] nums3 = new Solution350_v1().intersection(nums1, nums2);
        System.out.println(Arrays.toString(nums3));
    }
}